# -*- coding: utf-8 -*-            
# @Time : 2023/10/24 23:01
# @Author  : lining
# @FileName: 堆.py
"""
大根堆
建堆，数组存储,完全二叉树,从0开始，当前结点的父节点为n/2,向下取整
"""
class BinaryHeap:
    def __init__(self):
        # 从0开始存储，完全二叉树
        self.heap = []

    # 往队尾插入新节点
    def insert(self,value):
        # 插到尾部
        self.heap.append(value)
        # 向上调整
        self.heapifyUp(len(self.heap)-1)

    # 向上调整,自下而上建堆
    def heapifyUp(self,length):
        """
        :param length: 当前元素所在数组的下标
        :return:
        """
        # 前面的节点已经是大根堆。当前节点的父节点是n/2,向下取整
        while length>0:
            # 区分奇数偶数，
            if length%2 == 0:
                length_parent = int(length / 2)-1
            else:
                length_parent = int(length / 2)
            # 大于父节点交换
            if self.heap[length] > self.heap[length_parent]:
                self.heap[length], self.heap[length_parent]=self.heap[length_parent],self.heap[length]
                # 再继续和父节点的父节点比较
                length = length_parent
                continue
            # 小于父节点，终止,因为前面已经是大根堆，所以不用再比下去了
            break

    # 向下调整，自上而下建堆
    def heapifyDown(self, heap_list):
        """
        大根堆，向下调整要和左右子树较大的交换,下标从0开始
        :param self:
        :param heap_list:传入一个数组
        :return:
        """
        current = len(heap_list)
        while current >= 0:
            if current == len(heap_list):
                # 区分奇数偶数--偶数只有左子树，奇数有右子树，current取到最后一个节点的父节点的下标
                current = int((len(heap_list) - 1) / 2) if len(heap_list) % 2 == 0 else int((len(heap_list) - 1) / 2) - 1
                left = current * 2 + 1
                # 没有右子树
                if len(heap_list) % 2 == 0:
                    # 左子树和父节点的大小比较
                    if heap_list[current]<heap_list[left]:
                        heap_list[left],heap_list[current] = heap_list[current], heap_list[left]
                        current = current -1
            # 左子树
            left = current * 2 + 1
            # 右子树
            right = current * 2 + 2
            # 有左右子树
            max_value = left if heap_list[left]>heap_list[right] else right
            heap_list[max_value], heap_list[current] = heap_list[current], heap_list[max_value]
            current = current - 1


a = [1,2,3,4,5,6]
b = BinaryHeap()
# for i in a:
# #     b.insert(i)
b.heapifyDown(a)
print(a)